package day19;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/19 9:14
 */

/**
 * 给定一个字符串数组 words，找出 words 中所有的前缀都在 words 中的最长字符串。
 *
 * 例如，令 words = ["a", "app", "ap"]。字符串 "app" 含前缀 "ap" 和 "a" ，都在 words 中。
 * 返回符合上述要求的字符串。如果存在多个（符合条件的）相同长度的字符串，返回字典序中最小的字符串，如果这样的字符串不存在，返回 ""。
 *
 *
 *
 * 示例 1:
 *
 * 输入： words = ["k","ki","kir","kira", "kiran"]
 * 输出： "kiran"
 * 解释： "kiran" 含前缀 "kira"、 "kir"、 "ki"、 和 "k"，这些前缀都出现在 words 中。
 * 示例 2:
 *
 * 输入： words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
 * 输出： "apple"
 * 解释： "apple" 和 "apply" 都在 words 中含有各自的所有前缀。
 * 然而，"apple" 在字典序中更小，所以我们返回之。
 * 示例 3:
 *
 * 输入： words = ["abc", "bc", "ab", "qwe"]
 * 输出： ""
 *
 */
public class Solution2 {
    public String longestWord(String[] words) {
        Trie trie = new Trie();
        trie.insert(words);
        String str = "";
        loop:for (String word : words) {
            for (int i = 1; i <= word.length(); i++) {
                if(!trie.search(word.substring(0,i))){
                    continue loop;
                }
            }
            if(str.equals("")){
                str = word;
            }else {
                if(word.length()>str.length()){
                    str = word;
                }else if(word.length()==str.length()){
                    for (int i = 0; i < word.length(); i++) {
                        if(word.charAt(i)<str.charAt(i)){
                            str = word;
                            break;
                        }else if(word.charAt(i)>str.charAt(i)){
                            break;
                        }
                    }
                }
            }
        }
        return str;
    }
}
class Trie{
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    public void insert(String[] words) {
        for (String word : words) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                int index = ch - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.isEnd = true;
        }
    }
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}
